CS154 FINAL EXAM SOLUTIONS
Part I (True/False)

1.  True   Most introductory programming classes give a high-level algorithm to
	   determine if a number is prime.

2.  True   Suppose, to the contrary, that we have an algorithm to determine
	   if an r.e. language has property, P.  Then we can use the same algorithm
	   to determine if a CFL has property, P.  This is a contradiction.

3.  False  In the text is an example of a set that is r.e. but not recursive.
	   Therefore its complement is not r.e.

4.  False  The union of sets makes sense; the union of strings is nonsense.

5.  False  See page 147.

6.  True   Since R is regular, R is context free.  Therefore R satisfies Ogden's
	   lemma.

7.  False  Consider any non-regular set and its complement (which must be
	   non-regular).  Their union is the set of all strings, which is regular.

8.  True   The algorithm shown in class for converting a PDA, M, to a new PDA that
	   accepts the complement of what M accepts preserves determinism.

9.  False  See page 135.

10. True   The algorithm always says yes, because every CFL is recursive (we may
	   use the CYK algorithm to test for membership in a CFL).

11. True   The union of two regular sets is regular, and every regular set is
	   recursive.

12. True   Suppose, to the contrary, that R∪S is regular.  Intersect with R,
	   which is regular, to get a regular set.  But this set is S, which
	   is not regular.  Contradiction.

		     i k j m
13. True   This is {a b b c  | j=m, i=k}.

14. False  Suppose the problem, P, is "Determine whether an integer, n, is even."
	   I will use this paradigm to show that the problem is undecidable.
	   (1) Suppose we are given an integer, n.
	   (2) Write the following Pascal program:
		Program foo;
		begin
		    read(n);
		    while odd(n) do begin (* infinite loop *) end;
		end. (* halt *)
	      (* This program halts if and only if n is even *)
	   (3) Since the halting problem is undecidable, it is undecidable whether
	       n is even.
	   Since it is easy to determine if n is even, this paradigm is no good.
	   A correct paradigm is the following:
	   (1) Start with a general instance of the halting problem.
	   (2) Construct from that instance an instance of he problem, P.
	   (3) Say that since the halting problem is undecidable, P is undecidable.

15. False  Problem 1 on the midterm is an example of a set that is pumpable but
	   not regular.

16. False  rs is not a set.  It is a string.

17. True   A set is recursive if and only if both the set and its complement
	   are recursively enumerable

18. True   The algorithm given in class for constructing a PDA that accepts the
	   intersection of a regular set with the language accepted by a PDA
	   preserves determinism.

19. True   CFL's are recursive because we may use the CYK algorithm to test for
	   membership in a CFL.  Since the intersection of 2 recursive sets is
	   recursive, the intersection of any finite number of recursive sets
	   is recursive.  Therefore the intersection of any finite number of CFL's
	   is recursive.

20. True   See page 179.

21. False  Rice's theorem says that it is undecidable whether an r.e. set contains
	   exactly 17 elements.
				CS154 FINAL EXAM SOLUTIONS

Part II (most problems)

1.  The upper bound we wanted was n n  states.  This is the number of states
				   1 2
    in the cross product of the set of states for L  and the set of states for L .
						   1				2

2a. The text proves that it is possible to build a deterministic 4-counter machine
    to accept any set.  A non-deterministic 4-counter machine can guess an entire
    computation of this machine and then proceed to check it.

    First the non-deterministic machine guesses a computation.  Then a DFA
    checks the non-counter operations in the guessed computation.  Then the
    first one-counter machine checks the operations of the first counter in
    the guessed computation.   Then second one-counter machine checks the
    operations of the second counter in the guessed computation.  And so on.
    
    If there is an error anywhere in the computation, then the machine rejects.
    If there is no error, then the machine accepts.

3a. No.  Intersect with (*[*)*]*.  Then apply the pumping lemma for CFL's.

3b. This is not context-free, either.  Intersect with (*)*0*.  Then apply
    the pumping lemma for CFL's.

4.  Start with an A on the stack.  Each time you read a 0 push the next letter
    of the alphabet on the stack.  If there is a Q on the top of the stack then
    go to an accepting state.  If you read anything when in this state go to a
    dead state and ignore further input.

6.  No.  Deterministic PDA's can't accept arbitrary CFL's.

8a. No.  One of the homework solutions showed that any set can be written
    as the infinite union of r.e. sets:


		S  =   ∪ {n}
		      nεS

8b. Yes.  Guess a Turing machine.  Check to see if it is in S.  Then run the
    guessed machine on input i.  If it accepts, then accept.  Otherwise reject.
    (This is non-deterministic.)

8c. Let player 1 play for 1 millisecond.  Then let player 1 play for 1 millisecond
    and let player two play for 1 millisecond.  Then let player 1 play for 1
    millisecond, let player 2 play for 1 millisecond, and let player 3 play for
    1 millisecond.  And so on.

9a. No.  Start with the problem of determining whether Turing machine, M, halts on
    input, i.  Build a new machine, M', that ignores its input and then
    simulates machine, M, on input, i; then it accepts.  M' accepts the empty
    set if M does not halt on input, i, and M' accepts all strings if M halts
    on input, i.  Since the code of M' is a positive integer, M' is tolerant
    if and only if M halts on i.  Thus if we can determine whether a number is
    tolerant we can solve the halting problem.

9b. Yes.  A non-deterministic machine can accept the set of tolerant numbers.
    If the input is n, then guess n numbers.  Check to see if the machine whose
    code number is n accepts these n numbers.  If so, accept.  Otherwise reject.

9c. No.  Suppose, to the contrary, that the set of intolerant numbers is r.e.
    But the set of tolerant numbers is r.e. by part (b).  Therefore the set of
    tolerant numbers is recursive (since the set and its complement are r.e.).
    This is a contradiction.

9d. Intersect with (ab)*.  Then run this set through a gsm that deletes all the
				 n
    b's.  The resulting set is {a | n is tolerant}.  But this set is not
    recursive.  Therefore it is not regular.  Therefore the original set is
    not regular.

9e. No.  You will need to look at the recursion theorem on page 208.

    Start with the problem of determining whether Turing machine, M, halts on
    input, i.  For any integer, j, we may build a Turing machine, M, that rejects
    if its input is not between 1 and j; otherwise it simulates machine, M, on input,
    i; and then accepts.  This machine accepts exactly j inputs if and only if
    machine, M, halts on input, i.  Call the code number of this machine s(j).

    By the recursion theorem, there exists an integer, x , such that the machine
							0
    whose code is x  accepts the same set as the machine whose code is s(x ).
		   0							  0
    Because of how I defined the function, s, the machine whose code is s(x )
									   0
    accepts exactly x  inputs if and only if machine, M, halts on input, i.
		     0
    Therefore, the machine whose code is x  accepts exactly x  inputs if and
					  0		     0
    only if machine, M, halts on input, i.  That is, x  is snobbish if and only if
						      0
    machine, M, halts on input, i.

    Therefore, if we can determine whether a number is snobbish, then we can
    solve the halting problem.